package application;

import java.io.BufferedWriter;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.logging.Logger;

import application.Node;

/** @author siwy */

public class Algorithm {
	private final static Logger log = Logger.getLogger(Window.class.getName());
	private Node[] graph;
	private Node[] graphw;
	private int[] nodesColors;
	private int[] nodesColorsFrom0toN;
	private boolean success;
	private int usedColorNumber;
	private ArrayList<Integer[]> colorsUserAnd0toN = new ArrayList<>();

	/**
	 * Zwraca czy algorytm pokolorował wierzchołki
	 * 
	 * @return
	 */
	public boolean wasAlgorithmSuccessful() {
		return success;
	}

	/**
	 * zwraca użytą liczbę kolorów
	 * 
	 * @return
	 */

	public int getUsedColorNumber() {
		return usedColorNumber;
	}

	/**
	 * Konstruktor
	 * 
	 * @param graph
	 *            graf na którym będzie dział algorytm, graf jest tablicą
	 *            wierzchołków
	 */
	public Algorithm(Node[] graph) {
		this.graph = graph;

	}

	/**
	 * Zwraca możliwe do przyjęcia przez wierzchołek kolory w postaci int od 0
	 * do (liczba kolorów-1)
	 * 
	 * @param nodeIndex
	 *            numer wierzchołka
	 * @return
	 */
	public ArrayList<Integer> getNodePossibleColorsNormalized(int nodeIndex) {

		ArrayList<Integer> tempArrayList = new ArrayList<Integer>();
		for (int tempNodeColor : graph[nodeIndex].getPossibleColors()) {
			for (Integer[] tempColor : colorsUserAnd0toN) {
				if (tempColor[0] == tempNodeColor) {
					tempArrayList.add(tempColor[1]);
					break;
				}

			}

		}

		System.out.println(tempArrayList.toString());
		return tempArrayList;
	}

	/**
	 * Zwraca arraylistę możliwych do przyjęcia przez wierzchołki kolorów w postaci int od 0
	 * do (liczba kolorów-1), pierwsza arraylista składa się z wierzchołków, druga z mozliwych do przyjęcia przez nich kolorów
	 * @return
	 */
	public ArrayList<ArrayList<Integer>> getAllNodePossibleColorsNormalized() {
		ArrayList<ArrayList<Integer>> temp = new ArrayList<>();
		for (int i = 1; i < graph.length; i++) {
			temp.add(getNodePossibleColorsNormalized(i));
		}
		return temp;
	}

	/**
	 * Funkcja zwraca tablicę zawierającą numery kolorów odpowiadające kolejnym
	 * numerom wierzchołków UWAGA: 0 to pierwszy kolor a n-1 ostatni
	 * 
	 * @return tablica intów reprezentująch kolory
	 */
	public int[] getColorsOfNodesNormalized() {
		return nodesColorsFrom0toN;

	}

	/**
	 * Zapisuje wyniki algorytmu do pliku
	 * 
	 * @param fileOutput
	 *            plik wynikowy
	 */

	public void saveResultsToFile(File fileOutput) {
		try {

			BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(
					new FileOutputStream(fileOutput)));
			try {
				if (success) {
					writer.write("Użyta liczba kolorów: " + usedColorNumber);
					writer.newLine();
					writer.write("Wierzchołek | przyjęty kolor | możliwe do przyjęcia kolory");
					writer.newLine();

					for (int i = 1; i < graph.length; i++) {

						writer.write(String.format("%11d | %14d | %s", i,
								nodesColors[i], graph[i].getPossibleColors()
										.toString()));
						writer.newLine();
					}
				} else {
					writer.write("Nie udało się pokolorować wierzchołków.");
					writer.newLine();
				}

				writer.close();

			} catch (IOException e) {

				e.printStackTrace();
			}
		} catch (FileNotFoundException e) {

			e.printStackTrace();
		}

	}

	/**
	 * comparator do sortowania na podstawie stopni wierzchołków w grafie graphw
	 * 
	 * 
	 */
	class NodeDegreeComparator implements Comparator<Integer> {
		@Override
		public int compare(Integer node1, Integer node2) {
			return (graphw[node1].getNodeDegree() - graphw[node2]
					.getNodeDegree());
		}

	}

	/**
	 * Comparator do sortowania kolorów
	 * 
	 */

	class ColorTabComparator implements Comparator<Integer[]> {
		@Override
		public int compare(Integer[] color1, Integer[] color2) {
			return (color1[0] - color2[0]);
		}

	}

	/**
	 * Funkcja wykonująca algorytm na podanym w konstruktorze klasy grafie
	 */

	public void doAlgorithm() {
		// algorytm z normalną kolejnością sortowania wierzchołków
		int algWithNormalOrder = doAlgorithmWithOrder(false);

		int[] nodesColorsbackup = nodesColors.clone();
		int[] nodesColorsFrom0toNbackup = nodesColorsFrom0toN.clone();

		// algorytm ze zmienioną kolejnością sortowania wierzchołków o równych
		// stopniach
		int algWithDiffrentOrder = doAlgorithmWithOrder(true);

		System.out.println("wynik algorytmu z normalną kolejnością: "
				+ algWithNormalOrder);
		System.out.println("wynik algorytmu z odwrotną kolejnością: "
				+ algWithDiffrentOrder);
		if (algWithNormalOrder == -1) {
			if (algWithDiffrentOrder != -1) { // com2
				success = true;
				usedColorNumber = algWithDiffrentOrder;
			} else { // oba źle
				success = false;
			}
		} else {
			if (algWithDiffrentOrder == -1) { // com1
				success = true;
				usedColorNumber = algWithNormalOrder;
				nodesColors = nodesColorsbackup.clone();
				nodesColorsFrom0toN = nodesColorsFrom0toNbackup.clone();
			} else { // oba ok, por wyniki
				success = true;
				if (algWithNormalOrder > algWithDiffrentOrder) {
					usedColorNumber = algWithDiffrentOrder;
				} else {
					usedColorNumber = algWithNormalOrder;
					nodesColors = nodesColorsbackup.clone();
					nodesColorsFrom0toN = nodesColorsFrom0toNbackup.clone();
				}
			}
		}

	}

	/**
	 * Funkcja wykonuje algorytm z możliwością odwrócenia kolejności sortowania
	 * części listy wierzchołków, których stopnie są równe. Sortowanie
	 * wykonywane jest na listach kolorów zawierających wierzchołki mogące
	 * przyjąć dany kolor.
	 * 
	 * @param diffrentOrder
	 *            czy odwrócić kolejność sortowania wierzchołków o równych
	 *            stopniach
	 * @return
	 */
	@SuppressWarnings("unchecked")
	private int doAlgorithmWithOrder(boolean diffrentOrder) {
		nodesColors = new int[graph.length];
		nodesColorsFrom0toN = new int[graph.length];
		// graf gw=g
		graphw = new Node[graph.length];
		for (int i = 1; i < graph.length; i++) {
			graphw[i] = new Node(graph[i]);
		}

		// wyznaczamy zbiór LL
		Set<Integer> colorsSet = new HashSet<Integer>();
		for (int i = 1; i < graph.length; i++) {
			colorsSet.addAll(graph[i].getPossibleColors());
		}

		ArrayList<Integer[]> colors = new ArrayList<>();
		Iterator<Integer> iterator = colorsSet.iterator();

		while (iterator.hasNext()) {
			Integer[] colorItem = new Integer[2];
			colorItem[0] = iterator.next(); // kolor usera
			colors.add(colorItem);
		}
		Collections.sort(colors, new ColorTabComparator());
		log.info("kolor0: " + colors.get(0)[0]);
		log.info("kolor1: " + colors.get(1)[0]);
		int tempColorNumber = 0;
		for (Integer[] colorItem : colors) {
			colorItem[1] = tempColorNumber;// nasz kolor po kolei
			tempColorNumber++;
		}
		colorsUserAnd0toN = (ArrayList<Integer[]>) colors.clone();
		log.info("Wyznaczona lista kolorów LL ma długość " + colors.size());

		// wyznaczamy zbiór Qi
		// ArrayList<Integer>[] nodesWithColor=new ArrayList[colors.size()];
		ArrayList<ArrayList<Integer>> nodesWithColor = new ArrayList<>();

		for (Integer[] color : colors) {
			nodesWithColor.add(new ArrayList<Integer>());
			for (int i = 1; i < graph.length; i++) {
				if (graph[i].hasPossibleColor(color[0])) {
					nodesWithColor.get(color[1]).add(i);
				}
				log.info("zbiór Qi[" + color[1] + "]="
						+ nodesWithColor.get(color[1]).toString());
			}

		}
		// pętla
		int iteration = 0;
		int numberNodesOfGraphw = graphw.length - 1;
		log.info("numberNodesOfGraphw: " + numberNodesOfGraphw);
		log.info("wchodzę w pętlę");
		while (!colors.isEmpty() && numberNodesOfGraphw > 0) {
			iteration++;
			log.info("Iteracja:" + iteration);
			// sortujemy
			for (int colorNumber = 0; colorNumber < nodesWithColor.size(); colorNumber++) {

				// System.out.println("sortowanie 1: "+nodesWithColor.get(colorNumber).toString());
				if (diffrentOrder) {
					Collections.reverse(nodesWithColor.get(colorNumber));
				}
				Collections.sort(nodesWithColor.get(colorNumber),
						new NodeDegreeComparator());
				// System.out.println("sortowanie 2: "+nodesWithColor.get(colorNumber).toString());
				log.info("Zbiór [" + colorNumber + "] posortowany: "
						+ nodesWithColor.get(colorNumber));

			}

			// wyznaczamy zbiory Si
			ArrayList<Integer>[] nodesWithColorIsolated = new ArrayList[colors
					.size()];
			for (int colorNumber = 0; colorNumber < nodesWithColorIsolated.length; colorNumber++) {
				nodesWithColorIsolated[colorNumber] = new ArrayList<Integer>();
				nodesWithColorIsolated[colorNumber].add(nodesWithColor.get(
						colorNumber).get(0));
				for (int i = 1; i < nodesWithColor.get(colorNumber).size(); i++) {
					int tempNode = nodesWithColor.get(colorNumber).get(i);
					boolean isConectedWithOtherNode = false;

					for (int nodeIsolated : nodesWithColorIsolated[colorNumber]) {
						if (graphw[nodeIsolated].hasAdjacentNode(tempNode)) {
							isConectedWithOtherNode = true;
							break;
						}
					}
					if (!isConectedWithOtherNode) {
						nodesWithColorIsolated[colorNumber].add(tempNode);
					}

				}
				log.info("zbiór Si[" + colorNumber + "]="
						+ nodesWithColorIsolated[colorNumber].toString());
			}

			// wybieramy najbardziej liczny zbiór Si
			int quantity = -1;
			int largestNodesWithColorIsolated = -1;
			for (int i = 0; i < nodesWithColorIsolated.length; i++) {
				if (nodesWithColorIsolated[i].size() > quantity) {
					largestNodesWithColorIsolated = i;
					quantity = nodesWithColorIsolated[i].size();
				}
			}
			log.info("Najbardziej liczny zbiór Si to S["
					+ largestNodesWithColorIsolated + "] z licznością:"
					+ quantity);
			// kolorowanie wierzchołków i usuwanie z grafu Gw i ze zbiorów Qi
			for (Integer nodeToColor : nodesWithColorIsolated[largestNodesWithColorIsolated]) {
				numberNodesOfGraphw--;
				int colorByUser = colors.get(largestNodesWithColorIsolated)[0];

				nodesColors[nodeToColor] = colorByUser;
				nodesColorsFrom0toN[nodeToColor] = colors
						.get(largestNodesWithColorIsolated)[1];
				log.info("Wierzchołek " + nodeToColor
						+ " pokolorowany na kolor: " + colorByUser);
				graphw[nodeToColor] = null;
				// usuwamy z list sąsiedztwa
				for (int i = 1; i < graphw.length; i++) {
					if (graphw[i] != null) {
						if (graphw[i].hasAdjacentNode(nodeToColor)) {
							graphw[i].removeAdjacentNode(nodeToColor);
							log.info("usunięto wierzchołek " + nodeToColor
									+ " z listy sądziedztwa wierzchołka " + i);
						}
					}

				}
				// usuwamy ze zbirów Qi

				for (int colorNumber = 0; colorNumber < nodesWithColor.size(); colorNumber++) {

					if (nodesWithColor.get(colorNumber).contains(nodeToColor)) {
						nodesWithColor.get(colorNumber).remove(nodeToColor);
						log.info("usunięto wierzchołek " + nodeToColor
								+ " z Q[" + colorNumber + "]");
					}

				}
			}

			// usuwam kolor z LL
			colors.remove(largestNodesWithColorIsolated);
			// usuwam odpowiadającuy m zbiór Qi
			nodesWithColor.remove(largestNodesWithColorIsolated);
			log.info("kolor " + largestNodesWithColorIsolated
					+ "usunięty ze zbioru kolorów możliwych do przyjęcia");
			// sprawdzam pustość zbiorów Qi i usuwam ewentualnie kolor

			int colorNumber = 0;
			for (Iterator<ArrayList<Integer>> iteratorNodes = nodesWithColor
					.iterator(); iteratorNodes.hasNext();) {
				ArrayList<Integer> tempNode = iteratorNodes.next();

				if (tempNode.isEmpty()) {
					colors.remove(colorNumber);
					iteratorNodes.remove();

					log.info("kolor "
							+ colorNumber
							+ "usunięty ze zbioru kolorów możliwych do przyjęcia");
					colorNumber--;
				}
				colorNumber++;
			}

		}

		log.info("pętla zakończona");
		if (!(numberNodesOfGraphw > 0)) {
			// udało się
			log.info("wynik: przyporządkowano wierzchołkom kolory :)");

			return iteration;
		} else {
			// nie udało się
			log.info("wynik: skończyły się kolory :(");
			return -1;
		}

	}

}
